package mao.leetcode.others;

import java.util.*;

public class leetcode133 {

        public Node cloneGraph(Node node) {
                return cloneGraphDFS(node,new HashMap<>());
        }

        public Node cloneGraphDFS(Node node, Map<Node,Node> map) {
            if (node == null) return null;
            if (map.containsKey(node))
                return map.get(node);
            Node copy = new Node(node.val,new ArrayList<>());
            map.put(node,copy); //map里面有，说明这个node已经在栈中展开了
            for (Node n:node.neighbors) {
                copy.neighbors.add(cloneGraphDFS(n,map));
            }
            return copy;

        }

        static Map<Node,Node> map = new HashMap<>();
        static Set<Node> visited = new HashSet<>();
    public Node cloneGraphBFS(Node node) {
        if (visited.contains(node))
            return map.get(node);
        Node copy;
        if (map.containsKey(node))
            copy = map.get(node);
        else {
            copy = new Node(node.val, new ArrayList<>());
            map.put(node, copy);
        }

        for (Node n:node.neighbors) {
            if (map.containsKey(n))
                copy.neighbors.add(map.get(n));
            else {
                Node node_1 = new Node(n.val, new ArrayList<>());
                copy.neighbors.add(node_1);
                map.put(n,node_1);
            }
        }
        visited.add(node);
        for (Node n: node.neighbors) {
            cloneGraphBFS(n);
        }
        return copy;
    }
}

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

